<!DOCTYPE html>
        <html>
        <head>
            <meta charset="UTF-8">
            <title>&#x7b97;&#x6cd5;&#x5206;&#x6790;&#x4e0e;&#x8bbe;&#x8ba1;&#x7b2c;&#x516d;&#x6b21;&#x4f5c;&#x4e1a;</title>
            <style>
/* From extension vscode.github */
/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

.vscode-dark img[src$=\#gh-light-mode-only],
.vscode-light img[src$=\#gh-dark-mode-only],
.vscode-high-contrast:not(.vscode-high-contrast-light) img[src$=\#gh-light-mode-only],
.vscode-high-contrast-light img[src$=\#gh-dark-mode-only] {
	display: none;
}

</style>
            
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item {
    list-style-type: none;
}

.task-list-item-checkbox {
    margin-left: -20px;
    vertical-align: middle;
    pointer-events: none;
}
</style>
<style>
:root {
  --color-note: #0969da;
  --color-tip: #1a7f37;
  --color-warning: #9a6700;
  --color-severe: #bc4c00;
  --color-caution: #d1242f;
  --color-important: #8250df;
}

</style>
<style>
@media (prefers-color-scheme: dark) {
  :root {
    --color-note: #2f81f7;
    --color-tip: #3fb950;
    --color-warning: #d29922;
    --color-severe: #db6d28;
    --color-caution: #f85149;
    --color-important: #a371f7;
  }
}

</style>
<style>
.markdown-alert {
  padding: 0.5rem 1rem;
  margin-bottom: 16px;
  color: inherit;
  border-left: .25em solid #888;
}

.markdown-alert>:first-child {
  margin-top: 0
}

.markdown-alert>:last-child {
  margin-bottom: 0
}

.markdown-alert .markdown-alert-title {
  display: flex;
  font-weight: 500;
  align-items: center;
  line-height: 1
}

.markdown-alert .markdown-alert-title .octicon {
  margin-right: 0.5rem;
  display: inline-block;
  overflow: visible !important;
  vertical-align: text-bottom;
  fill: currentColor;
}

.markdown-alert.markdown-alert-note {
  border-left-color: var(--color-note);
}

.markdown-alert.markdown-alert-note .markdown-alert-title {
  color: var(--color-note);
}

.markdown-alert.markdown-alert-important {
  border-left-color: var(--color-important);
}

.markdown-alert.markdown-alert-important .markdown-alert-title {
  color: var(--color-important);
}

.markdown-alert.markdown-alert-warning {
  border-left-color: var(--color-warning);
}

.markdown-alert.markdown-alert-warning .markdown-alert-title {
  color: var(--color-warning);
}

.markdown-alert.markdown-alert-tip {
  border-left-color: var(--color-tip);
}

.markdown-alert.markdown-alert-tip .markdown-alert-title {
  color: var(--color-tip);
}

.markdown-alert.markdown-alert-caution {
  border-left-color: var(--color-caution);
}

.markdown-alert.markdown-alert-caution .markdown-alert-title {
  color: var(--color-caution);
}

</style>
        
        </head>
        <body class="vscode-body vscode-light">
            <style>
pre{
    page-break-before:auto;
    page-break-after:auto;
    page-break-inside:avoid
}
</style>
<h1 id="算法分析与设计第六次作业">算法分析与设计第六次作业</h1>
<p>陈俊杰 22009201352</p>
<h2 id="432">4.3.2</h2>
<p>图中共有8个顶点，10条边，该图的最小生成树中应只有7条边，又因为其图所有的边权值均相等，因此最小生成树不唯一。可以穷举所有只含7条边的子图，检查其是否是最小生成树，由此可以列出所有的最小生成数。</p>
<p>基于上述思路，编写了以下Java程序。</p>
<pre><code class="language-java"><span class="hljs-keyword">package</span> Exercises.Chapter4;

<span class="hljs-keyword">import</span> edu.princeton.cs.algs4.EdgeWeightedGraph;
<span class="hljs-keyword">import</span> edu.princeton.cs.algs4.Edge;
<span class="hljs-keyword">import</span> edu.princeton.cs.algs4.QuickUnionUF;
<span class="hljs-keyword">import</span> java.util.Iterator;

<span class="hljs-keyword">public</span> <span class="hljs-keyword">class</span> <span class="hljs-title class_">e4_3_2</span> {
    <span class="hljs-keyword">private</span> <span class="hljs-type">int</span> count;
    
    <span class="hljs-keyword">public</span> <span class="hljs-title function_">e4_3_2</span><span class="hljs-params">()</span>{
        Edge edges[]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>[<span class="hljs-number">10</span>];
        edges=InitEdges(edges);
        count=<span class="hljs-number">0</span>;

        <span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> i=<span class="hljs-number">0</span>;i&lt;<span class="hljs-number">10</span>;i++){
            <span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> j=i+<span class="hljs-number">1</span>;j&lt;<span class="hljs-number">10</span>;j++){
                <span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> k=j+<span class="hljs-number">1</span>;k&lt;<span class="hljs-number">10</span>;k++){
                    EdgeWeightedGraph graph=<span class="hljs-keyword">new</span> <span class="hljs-title class_">EdgeWeightedGraph</span>(<span class="hljs-number">8</span>);
                    QuickUnionUF uf=<span class="hljs-keyword">new</span> <span class="hljs-title class_">QuickUnionUF</span>(<span class="hljs-number">8</span>);

                    <span class="hljs-keyword">for</span>(<span class="hljs-type">int</span> p=<span class="hljs-number">0</span>;p&lt;<span class="hljs-number">10</span>;p++){
                        <span class="hljs-keyword">if</span>(p!=i&amp;&amp;p!=j&amp;&amp;p!=k){
                            <span class="hljs-type">int</span> v=edges[p].either();
                            <span class="hljs-type">int</span> w=edges[p].other(v);
                            uf.union(v,w);
                            graph.addEdge(edges[p]);
                        }
                    }

                    <span class="hljs-keyword">if</span>(uf.count()==<span class="hljs-number">1</span>){
                        count++;
                        PrintGraph(graph);
                        System.out.println();
                    }
                   
                }
            }
        }

    }

    <span class="hljs-keyword">private</span> Edge[] InitEdges(Edge edges[]){
        edges[<span class="hljs-number">0</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">2</span>, <span class="hljs-number">5</span>, <span class="hljs-number">1</span>);
        edges[<span class="hljs-number">1</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">1</span>);
        edges[<span class="hljs-number">2</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">5</span>, <span class="hljs-number">6</span>, <span class="hljs-number">1</span>);
        edges[<span class="hljs-number">3</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">0</span>, <span class="hljs-number">3</span>, <span class="hljs-number">1</span>);
        edges[<span class="hljs-number">4</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">3</span>, <span class="hljs-number">6</span>, <span class="hljs-number">1</span>);
        edges[<span class="hljs-number">5</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>, <span class="hljs-number">1</span>);
        edges[<span class="hljs-number">6</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">1</span>);
        edges[<span class="hljs-number">7</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">6</span>, <span class="hljs-number">7</span>, <span class="hljs-number">1</span>);
        edges[<span class="hljs-number">8</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">1</span>, <span class="hljs-number">4</span>, <span class="hljs-number">1</span>);
        edges[<span class="hljs-number">9</span>]=<span class="hljs-keyword">new</span> <span class="hljs-title class_">Edge</span>(<span class="hljs-number">4</span>, <span class="hljs-number">7</span>, <span class="hljs-number">1</span>);
        
        <span class="hljs-keyword">return</span> edges;
    }

    <span class="hljs-keyword">public</span> <span class="hljs-type">int</span> <span class="hljs-title function_">Count</span><span class="hljs-params">()</span>{
        <span class="hljs-keyword">return</span> count;
    }

    <span class="hljs-keyword">private</span> <span class="hljs-type">boolean</span> <span class="hljs-title function_">HasEdge</span><span class="hljs-params">(EdgeWeightedGraph graph,<span class="hljs-type">int</span> v,<span class="hljs-type">int</span> w)</span>{
        Iterable&lt;Edge&gt; edges=graph.edges();
        Iterator&lt;Edge&gt; it=edges.iterator();
        
        <span class="hljs-keyword">do</span>{
            Edge e=it.next();
            <span class="hljs-type">int</span> e_v=e.either();
            <span class="hljs-type">int</span> e_w=e.other(e_v);

            <span class="hljs-keyword">if</span>(e_v==v&amp;&amp;e_w==w) <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
            <span class="hljs-keyword">if</span>(e_v==w&amp;&amp;e_w==v) <span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;
        }<span class="hljs-keyword">while</span>(it.hasNext());
        <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;
    }

    <span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title function_">PrintGraph</span><span class="hljs-params">(EdgeWeightedGraph graph)</span>{
        System.out.print(<span class="hljs-string">&quot;\t\t1\t&quot;</span>);
        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">0</span>, <span class="hljs-number">1</span>)) System.out.print(<span class="hljs-string">&quot;---\t&quot;</span>); 
        <span class="hljs-keyword">else</span> System.out.print(<span class="hljs-string">&quot;\t&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;2\n\t\t&quot;</span>);

        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">0</span>, <span class="hljs-number">3</span>)) System.out.print(<span class="hljs-string">&quot;|\t&quot;</span>);
        <span class="hljs-keyword">else</span> System.out.print(<span class="hljs-string">&quot;\t&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;\t&quot;</span>);
        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">1</span>, <span class="hljs-number">4</span>)) System.out.print(<span class="hljs-string">&quot;|&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;\t\n&quot;</span>);
        
        System.out.print(<span class="hljs-string">&quot;3\t&quot;</span>);
        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>)) System.out.print(<span class="hljs-string">&quot;---&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;\t4\t&quot;</span>);
        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>)) System.out.print(<span class="hljs-string">&quot;---&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;\t5\n&quot;</span>);

        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">2</span>, <span class="hljs-number">5</span>)) System.out.print(<span class="hljs-string">&quot;|&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;\t\t&quot;</span>);
        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">3</span>, <span class="hljs-number">6</span>)) System.out.print(<span class="hljs-string">&quot;|&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;\t\t&quot;</span>);
        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">4</span>, <span class="hljs-number">7</span>)) System.out.print(<span class="hljs-string">&quot;|&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;\n&quot;</span>);

        System.out.print(<span class="hljs-string">&quot;6\t&quot;</span>);
        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">5</span>, <span class="hljs-number">6</span>)) System.out.print(<span class="hljs-string">&quot;---&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;\t7\t&quot;</span>);
        <span class="hljs-keyword">if</span>(HasEdge(graph, <span class="hljs-number">6</span>, <span class="hljs-number">7</span>)) System.out.print(<span class="hljs-string">&quot;---&quot;</span>);
        System.out.print(<span class="hljs-string">&quot;\t8\n&quot;</span>);

    }

    <span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title function_">main</span><span class="hljs-params">(String[] args)</span> {
        e4_3_2 e=<span class="hljs-keyword">new</span> <span class="hljs-title class_">e4_3_2</span>();
        System.out.println(<span class="hljs-string">&quot;\ntotal MSTs:&quot;</span>+e.Count());
    }
}
</code></pre>
<p>运行得出的结果如下所示，共有56个不同的最小生成树。</p>
<pre><code>                1       ---     2
                                |
3       ---     4       ---     5
                                |
6       ---     7       ---     8

                1       ---     2
                                |
3       ---     4               5
                |               |
6       ---     7       ---     8

                1       ---     2
                                |
3       ---     4       ---     5
                |               |
6       ---     7               8

                1       ---     2
                                |
3       ---     4       ---     5
                |
6       ---     7       ---     8

                1               2
                |               |
3       ---     4       ---     5
                                |
6       ---     7       ---     8

                1       ---     2
                |               |
3       ---     4               5
                                |
6       ---     7       ---     8

                1       ---     2
                |
3       ---     4       ---     5
                                |
6       ---     7       ---     8

                1               2
                |               |
3       ---     4               5
                |               |
6       ---     7       ---     8

                1               2
                |               |
3       ---     4       ---     5
                |               |
6       ---     7               8

                1               2
                |               |
3       ---     4       ---     5
                |
6       ---     7       ---     8

                1       ---     2
                |               |
3       ---     4               5
                |               |
6       ---     7               8

                1       ---     2
                |
3       ---     4               5
                |               |
6       ---     7       ---     8

                1       ---     2
                |               |
3       ---     4               5
                |
6       ---     7       ---     8

                1       ---     2
                |
3       ---     4       ---     5
                |               |
6       ---     7               8

                1       ---     2
                |
3       ---     4       ---     5
                |
6       ---     7       ---     8

                1       ---     2
                                |
3               4       ---     5
|                               |
6       ---     7       ---     8

                1       ---     2
                                |
3               4               5
|               |               |
6       ---     7       ---     8

                1       ---     2
                                |
3               4       ---     5
|               |               |
6       ---     7               8

                1       ---     2
                                |
3               4       ---     5
|               |
6       ---     7       ---     8

                1               2
                |               |
3               4       ---     5
|                               |
6       ---     7       ---     8

                1       ---     2
                |               |
3               4               5
|                               |
6       ---     7       ---     8

                1       ---     2
                |
3               4       ---     5
|                               |
6       ---     7       ---     8

                1               2
                |               |
3               4               5
|               |               |
6       ---     7       ---     8

                1               2
                |               |
3               4       ---     5
|               |               |
6       ---     7               8

                1               2
                |               |
3               4       ---     5
|               |
6       ---     7       ---     8

                1       ---     2
                |               |
3               4               5
|               |               |
6       ---     7               8

                1       ---     2
                |
3               4               5
|               |               |
6       ---     7       ---     8

                1       ---     2
                |               |
3               4               5
|               |
6       ---     7       ---     8

                1       ---     2
                |
3               4       ---     5
|               |               |
6       ---     7               8

                1       ---     2
                |
3               4       ---     5
|               |
6       ---     7       ---     8

                1       ---     2
                                |
3       ---     4       ---     5
|                               |
6               7       ---     8

                1       ---     2
                                |
3       ---     4               5
|               |               |
6               7       ---     8

                1       ---     2
                                |
3       ---     4       ---     5
|               |               |
6               7               8

                1       ---     2
                                |
3       ---     4       ---     5
|               |
6               7       ---     8

                1               2
                |               |
3       ---     4       ---     5
|                               |
6               7       ---     8

                1       ---     2
                |               |
3       ---     4               5
|                               |
6               7       ---     8

                1       ---     2
                |
3       ---     4       ---     5
|                               |
6               7       ---     8

                1               2
                |               |
3       ---     4               5
|               |               |
6               7       ---     8

                1               2
                |               |
3       ---     4       ---     5
|               |               |
6               7               8

                1               2
                |               |
3       ---     4       ---     5
|               |
6               7       ---     8

                1       ---     2
                |               |
3       ---     4               5
|               |               |
6               7               8

                1       ---     2
                |
3       ---     4               5
|               |               |
6               7       ---     8

                1       ---     2
                |               |
3       ---     4               5
|               |
6               7       ---     8

                1       ---     2
                |
3       ---     4       ---     5
|               |               |
6               7               8

                1       ---     2
                |
3       ---     4       ---     5
|               |
6               7       ---     8

                1       ---     2
                                |
3       ---     4               5
|                               |
6       ---     7       ---     8

                1       ---     2
                                |
3       ---     4       ---     5
|                               |
6       ---     7               8

                1       ---     2
                                |
3       ---     4       ---     5
|
6       ---     7       ---     8

                1               2
                |               |
3       ---     4               5
|                               |
6       ---     7       ---     8

                1               2
                |               |
3       ---     4       ---     5
|                               |
6       ---     7               8

                1               2
                |               |
3       ---     4       ---     5
|
6       ---     7       ---     8

                1       ---     2
                |               |
3       ---     4               5
|                               |
6       ---     7               8

                1       ---     2
                |
3       ---     4               5
|                               |
6       ---     7       ---     8

                1       ---     2
                |               |
3       ---     4               5
|
6       ---     7       ---     8

                1       ---     2
                |
3       ---     4       ---     5
|                               |
6       ---     7               8

                1       ---     2
                |
3       ---     4       ---     5
|
6       ---     7       ---     8


total MSTs:56
</code></pre>
<h2 id="433">4.3.3</h2>
<p>由切分定理以及基于切分定理的最小生成树贪心算法可知，当图中所有边权重各不相同时，若给定任意切分，其横切边中的权重最小者必然唯一，由切分定理的出的最小生成树必然也是唯一的。</p>
<h2 id="4313">4.3.13</h2>
<p>该算法并不能解决最小生成树中含环的问题，若有以下含4个节点的图</p>
<pre><code>边（顶点对）    权重
1-2             1
1-4             3
2-4             2
3-4             4
</code></pre>
<p>若选定节点1为起始点，则生成由该算法生成的最小生成树步骤如下所示</p>
<pre><code>i   加入的边    权重    最近加入的顶点
1   1-2         1       2
2   2-4         2       4
3   1-4         3       4
4   3-4         4       3
</code></pre>
<p>生成的最小生成树中含环，不符合最小生成树定义。</p>

            
            
        </body>
        </html>